# 剑指Offer题解 - Day25
# 剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
1
2
2
限制：
0 <= 链表长度 <= 1000
思路：
按照题目要求，是将两个有序的链表合并为一个有序的链表。考虑使用双指针的方法进行求解。
首先我们需要创建一个新链表的伪头部节点。然后当两个链表l1和l2 的当前节点都不为空的时候，进行比较节点值的大小，将较小的节点赋值给新链表。当l1或者l2 为空时跳出循环，并将两个链表的剩余部分直接赋值给新链表，因为剩余链表的值也是有序并且比前面的值都更大。
# 双指针
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
let link = new ListNode(null); // 新链表的伪头部节点
let cur = link; // 指向新链表的当前节点
while(l1 && l2) {
if (l1.val <= l2.val) { // 将较小节点赋值给当前节点的next
cur.next = l1;
l1 = l1.next; // l1向前走一步
} else {
cur.next = l2;
l2 = l2.next; // l2向前走一步
}
cur = cur.next; // 当前节点向前走一步
}
cur.next = l1 ?? l2; // 将剩余链表赋值给当前节点的next
return link.next; // 返回伪头部节点的next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
- 时间复杂度 O(m + n)。
- 空间复杂度 O(1)。
分析：
创建一个新链表的伪头部节点，用来承载当前节点的指针指向。
因为我们不知道l1和l2 链表的长度，因为循环条件要确保两个链表的当前值都不为空。循环里主要是将较小节点赋值给当前节点的next ，同时新旧链表都向前进一步，进入一下次循环。
循环结束后，势必有一个链表为空。那么判断不为空的链表，将剩余节点赋值给当前节点的next 。就算两个链表同时为空，next的指向也是null 。
最后不能直接返回link，因为存在一个伪头部节点，需要返回下一个节点，也就是link.next 。
# 总结
处理链表问题，优先考虑使用双指针进行解决。
本题的复杂度方面，由于需要需要遍历两个链表并合并，因此时间复杂度是O(m + n) ；维护了常数大小的变量，因此时间复杂度是O(1)。